НУЛП, ІКНІ, САПР Тема оцінка підпис    Потокові алгоритми         № залікової:     Дискретні моделі в САПР  Викладач:       Мета роботи : метою даної лабораторної роботи є вивчення потокових алгоритмів. Короткі теоретичні відомості : Останнім часом значно зросла зацікавленість учених та практиків потоковими моделями. Це пов’язано із впровадженням та активним розвитком різноманітних територіально розподілених систем: трубопровідних, транспортних, телекомунікаційних та ін. Основою таких систем є певна мережа (мережа трубопроводів, доріг, каналів зв’язку тощо), в якій циркулюють певні потоки (потоки речовин, транспорту, даних тощо), тому задачі, які доводиться розв’язувати при проектуванні та експлуатації систем з мережною структурою, часто зводяться до розробки математичних моделей розподілу потоків та постановки і розв’язання відповідних оптимізаційних задач. Відомі моделі розподілу потоків у мережах базуються на поняттях теорії графів. Це пов’язано з тим, що граф дає можливість наочно відобразити структуру мережі, а параметри його вузлів і дуг – представити основними числовими характеристиками її елементів. Набір характеристик залежить від природи модельованої системи, а також характеру розв’язуваних задач, однак у потокових моделях їх, як правило, представляють такими параметрами, як зовнішній потік у вузлі, потік по дузі, пропускна здатність дуги, вартість передавання одиниці потоку по дузі тощо. Потокові задачі, як правило, зводяться до пошуку такого розподілу потоків у мережі, при якому б забезпечувався екстремум деякого критерію. При цьому мають враховуватися обмеження, що накладаються умовами збереження потоків у вузлах і неперевищення потоками пропускної здатності дуг. Типовими потоковими задачами є задача про потік мінімальної вартості, про максимальний потік, транспортна задача, задача про призначення та інші. Для їх розв’язання розроблено чимало ефективних алгоритмів, сформувався навіть відповідний напрям обчислювальних методів під назвою потокового програмування. Потік-визначає спосіб пересилання деяких об’єктів з одного пункту в інший. Розв’язання задачі потоку зводиться до таких основних підзадач: максимізація сумарного обсягу перевезень; мінімізація вартості пересилань предметів з одного пункту в інший; мінімізація часу перевезень в заданій системі.Реалізація алгоритму (Java) : int maxFlow = 0;//Початковий максимальний потік int pathFlow;//Тимчасовий потік int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1];//Залишкова матриця ваг графу /* Копіювання матриці ваг в залишуову матрицю */ for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++) { residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex]; } } /* Доки шлях існує знаходимо найкращий потік */ while (bfs(source ,destination, residualGraph)) { pathFlow = Integer.MAX_VALUE; for (v = destination; v != source; v = parent[v]) { u = parent[v]; pathFlow = Math.min(pathFlow, residualGraph[u][v]); } for (v = destination; v != source; v = parent[v]) { u = parent[v]; residualGraph[u][v] -= pathFlow; residualGraph[v][u] += pathFlow; System.out.println(v + " до " + u); } System.out.println(pathFlow); maxFlow += pathFlow; } return maxFlow;} Інструкція по експлуатації: Для роботи програми необхідно запустити файл Lab_3_DM.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю ваг, початкову та кінцеву точки потоку. Далі програма знаходить максимальний потік та виводить його значення. Граф: Результат виконання: ***HELP*** 0. Програма знаходить максимальний потік в графі! Для коректної роботи програми необ...